#include <stdio.h>

int getMiddle(int a[], int left, int right)
{
    int tmp=a[left];
    int l=left, r=right;
    while(l < r)
    {
        while((l<r) && (a[r]>=tmp))
        {
            r--;
        }
        if (l<r)
        {
            a[l++]=a[r];
        }

        while((l<r) && (a[l]<=tmp))
        {
            l++;
        }
        if(l<r)
        {
            a[r--]=a[l];
        }
    }

    a[l]=tmp;
    return l;
}

void sort(int a[], int left, int right)
{
    if(left >= right)
    {
        return;
    }

    int middle = getMiddle(a, left, right);
    sort(a, left, middle - 1);
    sort(a, middle + 1, right);
}

int main(int argc, char* argv[])
{
    int a[]= {1,3,2,4,6,8,5,7};
    int len=sizeof(a)/sizeof(a[0]);
    sort(a, 0, len-1);

    for(int i=0; i<len; i++)
    {
        printf("%d\t", a[i]);
    }
    printf("\n");

    return 0;
}